{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Insertion Sort List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: insertionSortList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #对链表进行插入排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定单个链表的头<meta charset=\"UTF-8\" />&nbsp;<code>head</code>&nbsp;，使用 <strong>插入排序</strong> 对链表进行排序，并返回&nbsp;<em>排序后链表的头</em>&nbsp;。</p>\n",
    "\n",
    "<p><strong>插入排序</strong>&nbsp;算法的步骤:</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。</li>\n",
    "\t<li>每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。</li>\n",
    "\t<li>重复直到所有输入数据插入完为止。</li>\n",
    "</ol>\n",
    "\n",
    "<p>下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。</p>\n",
    "\n",
    "<p>对链表进行插入排序。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/04/sort1linked-list.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [4,2,1,3]\n",
    "<strong>输出:</strong> [1,2,3,4]</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/04/sort2linked-list.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [-1,5,3,4,0]\n",
    "<strong>输出:</strong> [-1,0,3,4,5]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>列表中的节点数在&nbsp;<code>[1, 5000]</code>范围内</li>\n",
    "\t<li><code>-5000 &lt;= Node.val &lt;= 5000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [insertion-sort-list](https://leetcode.cn/problems/insertion-sort-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [insertion-sort-list](https://leetcode.cn/problems/insertion-sort-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,1,3]', '[-1,5,3,4,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def insertionSortList(self, head):\n",
    "    \"\"\"\n",
    "    :type head: ListNode\n",
    "    :rtype: ListNode\n",
    "    \"\"\"\n",
    "    sh = ListNode( float( \"-inf\" ) )\n",
    "\n",
    "    while head != None:\n",
    "      node, head = head, head.next\n",
    "      p, q = sh, sh.next\n",
    "      while q != None and node.val > q.val:\n",
    "        p, q = q, q.next\n",
    "      p.next, node.next = node, q\n",
    "\n",
    "    t, sh = sh, sh.next\n",
    "    t.next = None\n",
    "    return sh\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dummy = ListNode(0)\n",
    "        while head:\n",
    "            n = head\n",
    "            head = head.next\n",
    "            n.next = None\n",
    "            cur = dummy\n",
    "            while cur.next and cur.next.val < n.val:\n",
    "                cur = cur.next\n",
    "            if not cur.next:\n",
    "                cur.next = n\n",
    "            else:\n",
    "                t = cur.next\n",
    "                cur.next = n\n",
    "                n.next = t\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None:\n",
    "            return\n",
    "        pre_head = ListNode(-1)\n",
    "        p = head\n",
    "        while p:\n",
    "            q = pre_head.next\n",
    "            r = pre_head\n",
    "            while q and q.val <= p.val:\n",
    "                q = q.next\n",
    "                r = r.next\n",
    "            r.next,p.next,p = p,r.next,p.next\n",
    "        return pre_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return head\n",
    "        res = ListNode(None)\n",
    "        res.next = head\n",
    "        \n",
    "        now = head.next\n",
    "        head.next = None\n",
    "        \n",
    "        while now is not None:\n",
    "            p = res\n",
    "            cur = res.next\n",
    "            while cur is not None and cur.val<=now.val:\n",
    "                p = cur\n",
    "                cur = cur.next\n",
    "            p.next = now\n",
    "            tmp = now.next\n",
    "            now.next = cur\n",
    "            now = tmp\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        new_head = ListNode(head.val)\n",
    "        new_head.next = None\n",
    "        \n",
    "        while head.next:\n",
    "            val = head.next.val\n",
    "            temp = ListNode(val)\n",
    "            if val < new_head.val:\n",
    "                temp.next = new_head\n",
    "                new_head = temp\n",
    "            else:\n",
    "                now = new_head\n",
    "                while now.next:\n",
    "                    if val < now.next.val:\n",
    "                        temp.next = now.next\n",
    "                        now.next = temp\n",
    "                        break\n",
    "                    else:\n",
    "                        now = now.next\n",
    "                else:\n",
    "                    now.next = temp\n",
    "                    \n",
    "            head = head.next\n",
    "                \n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head == None:\n",
    "            return head\n",
    "        elif head.next == None:\n",
    "            return head\n",
    "        else:\n",
    "            start_node = ListNode(head.val)\n",
    "            end_node = None\n",
    "            num_list = [head.val]\n",
    "            start = head.next\n",
    "            while start != None:\n",
    "                if end_node == None:\n",
    "                    if start.val<start_node.val:\n",
    "                        t = start_node\n",
    "                        start_node = ListNode(start.val)\n",
    "                        start_node.next = t\n",
    "                        end_node = t\n",
    "                    else:\n",
    "                        end_node = ListNode(start.val)\n",
    "                        start_node.next = end_node\n",
    "                else:\n",
    "                    if end_node.val<=start.val:\n",
    "                        end_node.next = ListNode(start.val)\n",
    "                        end_node = end_node.next\n",
    "                    else:\n",
    "                        if start.val<start_node.val:\n",
    "                            t = start_node\n",
    "                            start_node = ListNode(start.val)\n",
    "                            start_node.next = t\n",
    "                        else:\n",
    "                            now = start_node.next\n",
    "                            parent = start_node\n",
    "                            \n",
    "                            while now.val<=start.val:\n",
    "                                now = now.next\n",
    "                                parent = parent.next\n",
    "                            t = ListNode(start.val)\n",
    "                            t.next = now\n",
    "                            parent.next = t\n",
    "                start = start.next\n",
    "            return start_node\n",
    "                            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        L = []\n",
    "        while head:\n",
    "            L.append(head.val)\n",
    "            head = head.next\n",
    "        L.sort()\n",
    "        chead = ListNode(0)\n",
    "        newhead = chead\n",
    "        for elem in L:\n",
    "            newhead.next = ListNode(elem)\n",
    "            newhead = newhead.next\n",
    "        return chead.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        h = head\n",
    "        res = []\n",
    "        while h:\n",
    "            res.append(h.val)\n",
    "            h = h.next\n",
    "        res.sort()\n",
    "        h = head\n",
    "        for i in res:\n",
    "            h.val = i\n",
    "            h = h.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        # 找个排头\n",
    "        dummy = ListNode(-1)\n",
    "        pre = dummy\n",
    "        # 依次拿head节点\n",
    "        cur = head\n",
    "        while cur:\n",
    "        \t# 把下一次节点保持下来\n",
    "            tmp = cur.next\n",
    "            # 找到插入的位置\n",
    "            while pre.next and pre.next.val < cur.val:\n",
    "                pre = pre.next\n",
    "            # 进行插入操作\n",
    "            cur.next = pre.next\n",
    "            pre.next = cur\n",
    "            pre= dummy\n",
    "            cur = tmp\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# class Solution:\n",
    "#     def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "#         dummy = ListNode(float('-inf'))\n",
    "#         curr, dummy.next = head, head\n",
    "#         while curr:\n",
    "#             if curr.next and curr.val <= curr.next.val:\n",
    "#                 curr = curr.next\n",
    "#                 continue\n",
    "            \n",
    "#             pre = dummy\n",
    "#             while pre.next.val < curr.next.val:\n",
    "#                 pre = pre.next\n",
    "            \n",
    "#             temp1 = curr.next\n",
    "#             temp2 = pre.next\n",
    "#             curr.next = temp2\n",
    "#             pre.next = temp1\n",
    "\n",
    "#             curr = curr.next\n",
    "#             pre = pre.next\n",
    "#             curr.next, pre.next = pre.next, curr.next\n",
    "        \n",
    "#         return dummy.next\n",
    "class Solution(object):\n",
    "    def insertionSortList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head is None:\n",
    "            return head\n",
    "        dummynode = ListNode(None)\n",
    "        dummynode.next = head\n",
    "        curr = head\n",
    "        while curr and curr.next:\n",
    "            if curr.val <= curr.next.val:\n",
    "                curr = curr.next\n",
    "                continue\n",
    "            \n",
    "            pre = dummynode\n",
    "            while pre.next.val < curr.next.val:\n",
    "                pre = pre.next\n",
    "            \n",
    "            temp = curr.next\n",
    "            curr.next = temp.next\n",
    "            temp.next = pre.next\n",
    "            pre.next = temp\n",
    "\n",
    "        return dummynode.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        c = head\n",
    "        now = c.next\n",
    "        lhead = ListNode(c.val)\n",
    "        lhead.next = None\n",
    "       \n",
    "        # if lhead.val>c.val:\n",
    "        #     lhead.next = c\n",
    "        #     lhead.next.next = None\n",
    "        # else:\n",
    "        #     temp = lhead\n",
    "        #     lhead = c\n",
    "        #     lhead.next = c\n",
    "        #     lhead.next.next = None\n",
    "        # print(lhead)\n",
    "    \n",
    "        while now:\n",
    "            temp2 = now.next\n",
    "            if now.val > lhead.val:\n",
    "                temp = now\n",
    "                temp.next = lhead\n",
    "                lhead = temp\n",
    "            else:\n",
    "                temp = lhead\n",
    "                while temp.next and temp.next.val > now.val:\n",
    "                    temp = temp.next\n",
    "                temp1 = temp.next\n",
    "                temp.next = now\n",
    "                now.next = temp1\n",
    "            now = temp2\n",
    "            # print(lhead, now)\n",
    "        a = b = lhead\n",
    "        # print(a)\n",
    "        temp = a.next.next\n",
    "        tou = a.next\n",
    "        tou.next = a\n",
    "        a.next = temp\n",
    "        wei = a\n",
    "        # wei.next = None\n",
    "        a = a.next\n",
    "        # print(tou,a)\n",
    "        while a:\n",
    "            ttt = a.next\n",
    "            a.next = tou\n",
    "            tou = a\n",
    "            wei.next = ttt\n",
    "            a = ttt\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        # 4 3 2 1\n",
    "        # 3 4 2 1\n",
    "        # 2 3 4 1\n",
    "        # while a:\n",
    "        #     tt = a.next\n",
    "        #     a.next = tou\n",
    "        #     tou = a\n",
    "        #     a = tt\n",
    "        #     print(tou)\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "        return tou\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        nhead = ListNode(None)\n",
    "        while head:\n",
    "            node = head\n",
    "            head = head.next\n",
    "            node.next = None\n",
    "            self.insert(nhead, node)\n",
    "        return nhead.next\n",
    "    \n",
    "    def insert(self, nhead, node):\n",
    "        work = nhead\n",
    "        while work.next and node.val > work.next.val:\n",
    "            work = work.next\n",
    "        node.next = work.next\n",
    "        work.next = node\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        cur = head\n",
    "        while(cur):\n",
    "            pre = dummy\n",
    "            while pre.next and pre.next.val <= cur.val:\n",
    "                pre = pre.next\n",
    "            tem = cur.next\n",
    "            cur.next = pre.next\n",
    "            pre.next = cur\n",
    "            cur = tem\n",
    "        return dummy.next\n",
    "                    \n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head \n",
    "        \n",
    "        cur = head \n",
    "        new_head = None \n",
    "        while cur is not None:\n",
    "            tmp = cur \n",
    "            cur = cur.next \n",
    "            tmp.next = None \n",
    "\n",
    "            if new_head is None:\n",
    "                new_head = tmp \n",
    "            else:\n",
    "                new_cur = new_head\n",
    "                pre = None \n",
    "                while new_cur is not None and new_cur.val < tmp.val:\n",
    "                    pre = new_cur \n",
    "                    new_cur = new_cur.next \n",
    "                if pre is None:\n",
    "                    tmp.next = new_cur\n",
    "                    new_head = tmp \n",
    "                else:\n",
    "                    tmp.next = pre.next \n",
    "                    pre.next = tmp \n",
    "        \n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        sortedNumPre = ListNode(0)\n",
    "        sortedNumPre.next = ListNode(head.val)\n",
    "        head = head.next\n",
    "        flag = 1\n",
    "\n",
    "        while head:\n",
    "            flag = 1\n",
    "            sortedNum = sortedNumPre\n",
    "            while sortedNum.next:\n",
    "                if head.val <= sortedNum.next.val:\n",
    "                    buff = sortedNum.next\n",
    "                    sortedNum.next = ListNode(head.val)\n",
    "                    sortedNum.next.next = buff\n",
    "                    flag = 0\n",
    "                    break\n",
    "                sortedNum = sortedNum.next\n",
    "            if flag:\n",
    "                sortedNum.next = ListNode(head.val)\n",
    "                sortedNum.next.next = None\n",
    "            head = head.next\n",
    "        return sortedNumPre.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        dummyHead = ListNode(0)\n",
    "        dummyHead.next = head\n",
    "        lastSorted = head\n",
    "        curr = head.next\n",
    "\n",
    "        while curr:\n",
    "            if lastSorted.val <= curr.val:\n",
    "                lastSorted = lastSorted.next\n",
    "            else:\n",
    "                prev = dummyHead\n",
    "                while prev.next.val <= curr.val:\n",
    "                    prev = prev.next\n",
    "                lastSorted.next = curr.next\n",
    "                curr.next = prev.next\n",
    "                prev.next = curr\n",
    "            curr = lastSorted.next\n",
    "        \n",
    "        return dummyHead.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head_ = ListNode(val=-5001, next=head)\n",
    "        # start = head_\n",
    "        end = head\n",
    "        # pre = start\n",
    "        while end.next:\n",
    "            start = head_\n",
    "            while end.next.val > start.val:\n",
    "                pre = start\n",
    "                start = start.next\n",
    "            if pre is end:\n",
    "                end = end.next\n",
    "            else:\n",
    "                if end.next.next:\n",
    "                    tmp = end.next.next\n",
    "                    pre.next = end.next\n",
    "                    end.next.next = start\n",
    "                    end.next = tmp\n",
    "                    \n",
    "        \n",
    "                    \n",
    "                    \n",
    "                else:\n",
    "                    pre.next = end.next\n",
    "                    end.next.next = start\n",
    "                    end.next =  None\n",
    "        return head_.next\n",
    "                    \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        dummy_head = ListNode(-1)\n",
    "        dummy_head.next = head\n",
    "        sorted_list = head\n",
    "        cur = head.next\n",
    "\n",
    "        while cur:\n",
    "            if sorted_list.val <= cur.val:\n",
    "                #将cur插入到sorted_list之后\n",
    "                sorted_list = sorted_list.next\n",
    "            else:\n",
    "                prev = dummy_head\n",
    "                while prev.next.val <= cur.val:\n",
    "                    prev = prev.next\n",
    "                #将cur插到链表中间\n",
    "                sorted_list.next = cur.next\n",
    "                cur.next = prev.next\n",
    "                prev.next = cur\n",
    "            cur = sorted_list.next\n",
    "\n",
    "        return dummy_head.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        res = []\n",
    "        while cur:\n",
    "            res.append(cur.val)\n",
    "            cur = cur.next\n",
    "        res.sort()\n",
    "        cur = head\n",
    "        for i in range(len(res)):\n",
    "            cur.val = res[i]\n",
    "            cur = cur.next\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        tpr=head\n",
    "        res=[]\n",
    "        while tpr:\n",
    "            res.append(tpr.val)\n",
    "            tpr=tpr.next\n",
    "        res.sort()\n",
    "        tpr=head\n",
    "        for i in range(len(res)):\n",
    "            tpr.val=res[i]\n",
    "            tpr=tpr.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        q = []\n",
    "\n",
    "        cur = head\n",
    "        while cur:\n",
    "            node = cur\n",
    "            cur = cur.next\n",
    "            node.next = None\n",
    "            q.append((node.val, node))\n",
    "        \n",
    "        q.sort(key = lambda x: x[0])\n",
    "\n",
    "        dummy = None\n",
    "        \n",
    "\n",
    "        while q:\n",
    "            node = q.pop()[1]\n",
    "            node.next = dummy\n",
    "            dummy = node\n",
    "        return dummy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def insert(h,n):\n",
    "            c=h\n",
    "            while c.next and c.next.val<n.val:\n",
    "                c=c.next\n",
    "            n.next=c.next\n",
    "            c.next=n\n",
    "\n",
    "        dummy=ListNode()\n",
    "        cur=head\n",
    "        while cur:\n",
    "            n=cur.next\n",
    "            insert(dummy,cur)\n",
    "            cur=n\n",
    "\n",
    "        return dummy.next\n",
    "\n",
    "           \n",
    "        return temp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(0, head)\n",
    "        pre, cur = head, head.next\n",
    "\n",
    "        while cur:\n",
    "            # 跳过满足从小到大排序的部分\n",
    "            if cur.val >= pre.val:\n",
    "                pre, cur = cur, cur.next\n",
    "                continue\n",
    "            # 后面的节点小于cur 需要插入到正确位置\n",
    "            # 错误代码，想想为什么\n",
    "            # temp = dummy.next\n",
    "            # while cur.val > temp.val:\n",
    "            \n",
    "            temp = dummy\n",
    "            while cur.val > temp.next.val:   # 想像temp带着cur一起走\n",
    "                temp = temp.next\n",
    "            # 结束while时 cur.val < temp.val 插入到前面\n",
    "            pre.next = cur.next\n",
    "            cur.next = temp.next\n",
    "            temp.next = cur\n",
    "            cur = pre.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        first = ListNode(0) #记录头节点前的节点 以防头节点变化，最后便于输出链表\n",
    "        first.next = head #表明first和头节点的关系\n",
    "        last = head\n",
    "        cur = head.next\n",
    "        while cur:\n",
    "            if cur.val >= last.val:\n",
    "                last = last.next #如果cur大于last 说明不用进行变化，那么last和cur各往前走一步\n",
    "            else:#需要进行变化\n",
    "                pre = first\n",
    "                while cur.val >= pre.next.val: #当pre.next的值比cur的值要小，pre的位置就往前走一步\n",
    "                    pre = pre.next\n",
    "                 #把cur拎出来插到pre给它占的位置后面，那么last直接跳过cur连接到下一节点\n",
    "                last.next = cur.next\n",
    "                cur.next = pre.next\n",
    "                pre.next = cur\n",
    "            cur = last.next #之前的cur已经完成，又要回到last.next帮它占的位置，往前走了\n",
    "        return first.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        paixu = []\n",
    "\n",
    "        while head:\n",
    "            paixu.append([head.val, head])\n",
    "            head = head.next\n",
    "\n",
    "        paixu.sort(key=lambda x: x[0])\n",
    "\n",
    "        for i in range(len(paixu) - 1):\n",
    "            paixu[i][1].next = paixu[i + 1][1]\n",
    "\n",
    "        paixu[-1][1].next = None\n",
    "\n",
    "        return paixu[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.error = 0\n",
    "    def insertionSortList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            self.error = 1\n",
    "            return None \n",
    "        if not head.next:\n",
    "            return head \n",
    "        pNode = self.insertionSortList(head.next)\n",
    "        head.next = None \n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = pNode \n",
    "        node = dummy \n",
    "        while node.next:\n",
    "            if head.val < node.next.val:\n",
    "                tmp = node.next \n",
    "                node.next = head \n",
    "                head.next = tmp \n",
    "                return dummy.next \n",
    "            else:\n",
    "                node = node.next \n",
    "        node.next = head\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        result = None\n",
    "        while(head != None):\n",
    "            if result == None:\n",
    "                result = ListNode(head.val)\n",
    "            elif head.val <= result.val:\n",
    "                temp = ListNode(head.val)\n",
    "                temp.next = result\n",
    "                result = temp\n",
    "            else:\n",
    "                temp = result\n",
    "                while(temp.next != None and temp.next.val <= head.val):\n",
    "                    temp = temp.next\n",
    "                nextnode = temp.next\n",
    "                temp.next = ListNode(head.val)\n",
    "                temp.next.next = nextnode\n",
    "            head = head.next\n",
    "\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
